/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ania2;

import ania2.engine.utils.ZobristHashTables;
import ania2.enums.Fields;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author pawel
 */
public class BrazilianMoveGenerator implements MoveGenerator {

    private static final long PERMITTED = BoardPosition.getPermitted();
    private final Fields[] fields = Fields.values();
    private final int[] directions = new int[]{-4, -5, 4, 5};
    private static final long WHITE_PROMOTION_LINE;
    private static final long BLACK_PROMOTION_LINE;
    private int longestCapture;    
    //przekątne "w prawo"
    private static final long DIAGONAL_G1H2 = (1L << 55) | (1L << 50);
    private static final long DIAGONAL_E1H4 = (1L << 56) | (1L << 51) | (1L << 46) | (1L << 41);
    private static final long DIAGONAL_C1H6 = (1L << 57) | (1L << 52) | (1L << 47) | (1L << 42) | (1L << 37) | (1L << 32);
    private static final long DIAGONAL_A1H8 = (1L << 58) | (1L << 53) | (1L << 48) | (1L << 43) | (1L << 38) | (1L << 33) | (1L << 28) | (1L << 23);
    private static final long DIAGONAL_A3F8 = (1L << 49) | (1L << 44) | (1L << 39) | (1L << 34) | (1L << 29) | (1L << 24);
    private static final long DIAGONAL_A5D8 = (1L << 40) | (1L << 35) | (1L << 30) | (1L << 25);
    private static final long DIAGONAL_A7B8 = (1L << 31) | (1L << 26);    
    //przekątne "w lewo"
    private static final long DIAGONAL_C1A3 = (1L << 57) | (1L << 53) | (1L << 49);
    private static final long DIAGONAL_E1A5 = (1L << 56) | (1L << 52) | (1L << 48) | (1L << 44) | (1L << 40);
    private static final long DIAGONAL_G1A7 = (1L << 55) | (1L << 51) | (1L << 47) | (1L << 43) | (1L << 39) | (1L << 35) | (1L << 31);
    private static final long DIAGONAL_H2B8 = (1L << 50) | (1L << 46) | (1L << 42) | (1L << 38) | (1L << 34) | (1L << 30) | (1L << 26);
    private static final long DIAGONAL_H4D8 = (1L << 41) | (1L << 37) | (1L << 33) | (1L << 29) | (1L << 25);
    private static final long DIAGONAL_H6F8 = (1L << 32) | (1L << 28) | (1L << 24);
    private static final long[] RIGHT_DIAGONALS = new long[64];
    private static final long[] LEFT_DIAGONALS = new long[64];
    private static final long[][] HASH_RANDOM_TABLE = ZobristHashTables.HASH_CODE_TABLE;
    private static final long[][] LOCK_RANDOM_TABLE = ZobristHashTables.LOCK_CODE_TABLE;
    

    static {
        char[] a = new char[64];
        for (int i = 0; i < 64; i++) {
            a[i] = '0';
        }
        a[Fields.B8.ordinal()] = '1';
        a[Fields.D8.ordinal()] = '1';
        a[Fields.F8.ordinal()] = '1';
        a[Fields.H8.ordinal()] = '1';
        WHITE_PROMOTION_LINE = Long.parseLong(String.valueOf(a), 2);
        a[Fields.A1.ordinal()] = '1';
        a[Fields.C1.ordinal()] = '1';
        a[Fields.E1.ordinal()] = '1';
        a[Fields.G1.ordinal()] = '1';
        BLACK_PROMOTION_LINE = Long.parseLong(String.valueOf(a), 2) & ~WHITE_PROMOTION_LINE;
        initDiagonals();
    }

    private static void initDiagonals() {
        RIGHT_DIAGONALS[8] = RIGHT_DIAGONALS[13] = DIAGONAL_G1H2;
        for (int i = 7; i <= 22; i += 5) {
            RIGHT_DIAGONALS[i] = DIAGONAL_E1H4;
        }
        for (int i = 6; i <= 31; i += 5) {
            RIGHT_DIAGONALS[i] = DIAGONAL_C1H6;
        }
        for (int i = 5; i <= 40; i += 5) {
            RIGHT_DIAGONALS[i] = DIAGONAL_A1H8;
        }
        for (int i = 14; i <= 39; i += 5) {
            RIGHT_DIAGONALS[i] = DIAGONAL_A3F8;
        }
        for (int i = 23; i <= 38; i += 5) {
            RIGHT_DIAGONALS[i] = DIAGONAL_A5D8;
        }
        RIGHT_DIAGONALS[32] = RIGHT_DIAGONALS[37] = DIAGONAL_A7B8;

        for (int i = 6; i <= 14; i += 4) {
            LEFT_DIAGONALS[i] = DIAGONAL_C1A3;
        }
        for (int i = 7; i <= 23; i += 4) {
            LEFT_DIAGONALS[i] = DIAGONAL_E1A5;
        }
        for (int i = 8; i <= 32; i += 4) {
            LEFT_DIAGONALS[i] = DIAGONAL_G1A7;
        }
        for (int i = 13; i <= 37; i += 4) {
            LEFT_DIAGONALS[i] = DIAGONAL_H2B8;
        }
        for (int i = 22; i <= 38; i += 4) {
            LEFT_DIAGONALS[i] = DIAGONAL_H4D8;
        }
        for (int i = 31; i <= 39; i += 4) {
            LEFT_DIAGONALS[i] = DIAGONAL_H6F8;
        }
    }

    public BrazilianMoveGenerator() {
    }

    public List<Move> generateMoves(BoardPosition position, boolean whiteTurn) {
        LinkedList<Move> moves = new LinkedList<Move>();
        long whitePieces = position.getWhitePieces();
        long blackPieces = position.getBlackPieces();
        long queens = position.getQueens();
        int hashCode = position.getHashCode();
        int lockCode = (int)position.getLockCode();
        longestCapture = 0;
        if (whiteTurn) {
            generateQueenCaptures(whitePieces, blackPieces, queens, moves, whiteTurn);
            generateCaptures(whitePieces, blackPieces, queens, moves, whiteTurn);
            if (moves.isEmpty()) {
                generateQueenMoves(whitePieces, blackPieces, queens, moves, whiteTurn, hashCode, lockCode);
                generateSimpleMoves(whitePieces, blackPieces, queens, moves, whiteTurn, hashCode, lockCode);
            } else {
                removeRedundantCaptures(moves, longestCapture);
            }
        } else {
            generateQueenCaptures(blackPieces, whitePieces, queens, moves, whiteTurn);
            generateCaptures(blackPieces, whitePieces, queens, moves, whiteTurn);
            if (moves.isEmpty()) {
                generateQueenMoves(blackPieces, whitePieces, queens, moves, whiteTurn, hashCode, lockCode);
                generateSimpleMoves(blackPieces, whitePieces, queens, moves, whiteTurn, hashCode, lockCode);
            } else {
                removeRedundantCaptures(moves, longestCapture);
            }
        }
       /* for(Move m : moves) {
            BoardPosition p = m.getPosition();
            int hash = p.getHashCode();
            int lock = p.getLockCode();
            p.computeHashAndLockCode();
            if(p.getHashCode()!=hash)
                System.err.println("hasz");
            if(p.getLockCode()!=lock)
                System.err.println("lock");
        }*/
        return moves;
    }

    public List<Move> generateCaptures(BoardPosition position, boolean whiteTurn) {
        LinkedList<Move> moves = new LinkedList<Move>();
        long whitePieces = position.getWhitePieces();
        long blackPieces = position.getBlackPieces();
        long queens = position.getQueens();
        longestCapture = 0;
        if (whiteTurn) {
            generateQueenCaptures(whitePieces, blackPieces, queens, moves, whiteTurn);
            generateCaptures(whitePieces, blackPieces, queens, moves, whiteTurn);
            if (!moves.isEmpty()) {
                removeRedundantCaptures(moves, longestCapture);
            }
        } else {
            generateQueenCaptures(blackPieces, whitePieces, queens, moves, whiteTurn);
            generateCaptures(blackPieces, whitePieces, queens, moves, whiteTurn);
            if (!moves.isEmpty()) {
                removeRedundantCaptures(moves, longestCapture);
            }
        }
        return moves;
    }

    private void generateSimpleMoves(long sideToMove, long opponent, long queens, List moves, boolean whiteTurn, int hashCode, int lockCode) {
        long unoccupied = ~(sideToMove | opponent) & PERMITTED;
        int dir1 = 4;
        int dir2 = 5;
        dir1 = (whiteTurn) ? dir1 : -dir1;
        dir2 = (whiteTurn) ? dir2 : -dir2;
        long pieces1 = Long.rotateLeft(unoccupied, dir1) & (sideToMove & ~queens);
        long pieces2 = Long.rotateLeft(unoccupied, dir2) & (sideToMove & ~queens);
        long sourcePiece1 = Long.highestOneBit(pieces1);
        long sourcePiece2 = Long.highestOneBit(pieces2);
        while (sourcePiece1 > 0) {
            pieces1 ^= sourcePiece1;
            long targetField = Long.rotateRight(sourcePiece1, dir1);
            long newSideToMove = sideToMove ^ (sourcePiece1 | targetField);
            long newQueens = queens;
            int sourceIndex = 64 - Long.toBinaryString(sourcePiece1).length();
            int targetIndex = 64 - Long.toBinaryString(targetField).length();
            Fields from = fields[sourceIndex];
            Fields to = fields[targetIndex];
            String notation = from.toString() + "-" + to.toString();
            //piece to queen promotion
            boolean promotion = false;
            if (whiteTurn && notation.charAt(notation.length() - 1) == '8') {
                newQueens |= (newSideToMove & WHITE_PROMOTION_LINE);
                promotion = true;
            } else if (!whiteTurn && notation.charAt(notation.length() - 1) == '1') {
                newQueens |= (newSideToMove & BLACK_PROMOTION_LINE);
                promotion = true;
            }
            BoardPosition newPosition;
            int newHashCode = hashCode;
            int newLockCode = lockCode;
            if(whiteTurn) {
                newPosition = new BoardPosition(newSideToMove, opponent, newQueens);
                int type = (promotion) ? 2 : 0;
                newHashCode ^= HASH_RANDOM_TABLE[sourceIndex][0] ^ HASH_RANDOM_TABLE[targetIndex][type];
                newLockCode ^= LOCK_RANDOM_TABLE[sourceIndex][0] ^ LOCK_RANDOM_TABLE[targetIndex][type];
            }
            else {
                newPosition = new BoardPosition(opponent, newSideToMove, newQueens);
                int type = (promotion) ? 3 : 1;
                newHashCode ^= HASH_RANDOM_TABLE[sourceIndex][1] ^ HASH_RANDOM_TABLE[targetIndex][type];
                newLockCode ^= LOCK_RANDOM_TABLE[sourceIndex][1] ^ LOCK_RANDOM_TABLE[targetIndex][type];
            }
            newPosition.setHashCode(newHashCode);
            newPosition.setLockCode(newLockCode);
            //newPosition.computeHashAndLockCode();
            /*if(newHashCode != newPosition.getHashCode()) {
                System.out.println("pozycja przed, ruch białych? "+whiteTurn+", gracz:");
                printSetFields(sideToMove);
                System.out.println("przeciwnik:");
                printSetFields(opponent);
                System.out.println("damki:");
                printSetFields(queens);
                System.out.println("hashCode="+hashCode);
                System.out.println(newPosition.toString());
                System.out.println("new hashCode="+newHashCode);
            }*/
            Move m = new Move(newPosition, from, to, notation, notation, promotion);
            moves.add(m);
            sourcePiece1 = Long.highestOneBit(pieces1);
        }
        while (sourcePiece2 > 0) {
            pieces2 ^= sourcePiece2;
            long targetField = Long.rotateRight(sourcePiece2, dir2);
            long newSideToMove = sideToMove ^ (sourcePiece2 | targetField);
            long newQueens = queens;
            int sourceIndex = 64 - Long.toBinaryString(sourcePiece2).length();
            int targetIndex = 64 - Long.toBinaryString(targetField).length();
            Fields from = fields[sourceIndex];
            Fields to = fields[targetIndex];
            String notation = from.toString() + "-" + to.toString();
            //piece to queen promotion
            boolean promotion = false;
            if (whiteTurn && notation.charAt(notation.length() - 1) == '8') {
                newQueens |= (newSideToMove & WHITE_PROMOTION_LINE);
                promotion = true;
            } else if (!whiteTurn && notation.charAt(notation.length() - 1) == '1') {
                newQueens |= (newSideToMove & BLACK_PROMOTION_LINE);
                promotion = true;
            }
            BoardPosition newPosition;
            int newHashCode = hashCode;
            int newLockCode = lockCode;
            if(whiteTurn) {
                newPosition = new BoardPosition(newSideToMove, opponent, newQueens);
                int type = (promotion) ? 2 : 0;
                newHashCode ^= HASH_RANDOM_TABLE[sourceIndex][0] ^ HASH_RANDOM_TABLE[targetIndex][type];
                newLockCode ^= LOCK_RANDOM_TABLE[sourceIndex][0] ^ LOCK_RANDOM_TABLE[targetIndex][type];
            }
            else {
                newPosition = new BoardPosition(opponent, newSideToMove, newQueens);
                int type = (promotion) ? 3 : 1;
                newHashCode ^= HASH_RANDOM_TABLE[sourceIndex][1] ^ HASH_RANDOM_TABLE[targetIndex][type];
                newLockCode ^= LOCK_RANDOM_TABLE[sourceIndex][1] ^ LOCK_RANDOM_TABLE[targetIndex][type];
            }
            newPosition.setHashCode(newHashCode);
            newPosition.setLockCode(newLockCode);
            //newPosition.computeHashAndLockCode();
            Move m = new Move(newPosition, from, to, notation, notation, promotion);
            moves.add(m);
            sourcePiece2 = Long.highestOneBit(pieces2);
        }


    }

    private void generateCaptures(long sideToMove, long opponent, long queens, List moves, boolean whiteTurn) {
        long unoccupied = ~(sideToMove | opponent) & PERMITTED;
        for (int dir : directions) {
            long neighbour = Long.rotateLeft(unoccupied, dir) & opponent;
            long source = Long.rotateLeft(neighbour, dir) & (sideToMove & ~queens);
            long sourcePiece = Long.highestOneBit(source);
            while (sourcePiece > 0) {
                source ^= sourcePiece;
                int index = 64 - Long.toBinaryString(sourcePiece).length();
                int targetIndex = index + 2 * dir;
                long targetField = Long.rotateRight(sourcePiece, 2 * dir);
                long newSideToMove = sideToMove ^ (sourcePiece | targetField);
                long newOpponent = opponent ^ (Long.rotateRight(sourcePiece, dir));
                long newQueens = queens & (newSideToMove | newOpponent);
                String notation = fields[index].toString() + "x" + fields[targetIndex].toString();
                nextCapture(targetField, newSideToMove, newOpponent, newQueens, notation, moves, -dir, whiteTurn);
                sourcePiece = Long.highestOneBit(source);
            }
        }
    }

    private void nextCapture(long piece, long sideToMove, long opponent, long queens,
            String notation, List moves, int forbiddenDirection, boolean whiteTurn) {
        boolean finalCapture = true;
        long unoccupied = ~(sideToMove | opponent) & PERMITTED;
        for (int dir : directions) {
            if (dir == forbiddenDirection) {
                continue;
            }
            long captured = Long.rotateRight(piece, dir) & opponent;
            long targetField = Long.rotateRight(captured, dir) & unoccupied;
            if (targetField != 0) {
                finalCapture = false;
                int targetIndex = 64 - Long.toBinaryString(targetField).length();
                long newSideToMove = sideToMove ^ (piece | targetField);
                long newOpponent = opponent ^ captured;
                long newQueens = queens & (newSideToMove | newOpponent);
                String newNotation = notation + "x" + fields[targetIndex].toString();
                nextCapture(targetField, newSideToMove, newOpponent, newQueens, newNotation, moves, -dir, whiteTurn);
            }
        }
        if (finalCapture) {
            if (notation.length() < longestCapture) {
                return;
            } else {
                longestCapture = notation.length();
            }
            Fields source = Fields.valueOf(notation.substring(0, 2));
            Fields target = Fields.valueOf(notation.substring(notation.length() - 2, notation.length()));
            String shortNotation = source.toString() + "x" + target.toString();
            //piece to queen promotion
            boolean promotion = false;
            if (whiteTurn && shortNotation.charAt(shortNotation.length() - 1) == '8') {
                queens |= (sideToMove & WHITE_PROMOTION_LINE);
                promotion = true;
            } else if (!whiteTurn && shortNotation.charAt(shortNotation.length() - 1) == '1') {
                queens |= (sideToMove & BLACK_PROMOTION_LINE);
                promotion = true;
            }
            BoardPosition position;
            if(whiteTurn)
                position= new BoardPosition(sideToMove, opponent, queens);
            else
                position= new BoardPosition(opponent, sideToMove, queens);
            position.computeHashAndLockCode();
            Move m = new Move(position, source, target, notation, shortNotation, promotion);
            if (promotion) {
                moves.add(0, m);
            } else {
                moves.add(m);
            }
        }
    }

    private void generateQueenCaptures(long sideToMove, long opponent, long queens, List moves, boolean whiteTurn) {
        long ourQueens = sideToMove & queens;
        if (Long.highestOneBit(ourQueens) == 0) {
            return;
        }
        long unoccupied = ~(sideToMove | opponent) & PERMITTED;
        long queen = Long.highestOneBit(ourQueens);
        while (queen > 0) {
            ourQueens ^= queen;
            int index = 64 - Long.toBinaryString(queen).length();
            long rightDiagonal = RIGHT_DIAGONALS[index];
            long leftDiagonal = LEFT_DIAGONALS[index];
            long opponentRightDiag = opponent & rightDiagonal;
            long opponentLeftDiag = opponent & leftDiagonal;
            long freeRightDiag = unoccupied & rightDiagonal;
            long freeLeftDiag = unoccupied & leftDiagonal;
            //w prawo do góry
            if (Long.lowestOneBit(opponentRightDiag) < queen && freeRightDiag != 0) {
                long tmp = Long.rotateRight(queen, 5);
                while ((tmp & freeRightDiag) != 0) {
                    tmp = Long.rotateRight(tmp, 5);
                }
                if ((tmp & opponentRightDiag) == tmp) {
                    long tmp2 = Long.rotateRight(tmp, 5) & freeRightDiag;
                    while (tmp2 != 0) {
                        //bicie piona tmp na tmp2
                        long newSideToMove = sideToMove ^ (queen | tmp2);
                        long newOpponent = opponent ^ tmp;
                        long newQueens = queens ^ (queen | (tmp&queens) | tmp2);
                        int targetIndex = 64 - Long.toBinaryString(tmp2).length();
                        String notation = fields[index].toString() + "x" + fields[targetIndex].toString();
                        nextQueenCapture(tmp2, newSideToMove, newOpponent, newQueens, notation, moves, -5, whiteTurn);
                        tmp2 = Long.rotateRight(tmp2, 5) & freeRightDiag;
                    }
                }
            }
            //w lewo do dołu
            if (Long.highestOneBit(opponentRightDiag) > queen && freeRightDiag != 0) {
                long tmp = Long.rotateLeft(queen, 5);
                while ((tmp & freeRightDiag) != 0) {
                    tmp = Long.rotateLeft(tmp, 5);
                }
                if ((tmp & opponentRightDiag) == tmp) {
                    long tmp2 = Long.rotateLeft(tmp, 5) & freeRightDiag;
                    while (tmp2 != 0) {
                        //bicie piona tmp na tmp2
                        long newSideToMove = sideToMove ^ (queen | tmp2);
                        long newOpponent = opponent ^ tmp;
                        long newQueens = queens ^ (queen | (tmp&queens) | tmp2);
                        int targetIndex = 64 - Long.toBinaryString(tmp2).length();
                        String notation = fields[index].toString() + "x" + fields[targetIndex].toString();
                        nextQueenCapture(tmp2, newSideToMove, newOpponent, newQueens, notation, moves, 5, whiteTurn);
                        tmp2 = Long.rotateLeft(tmp2, 5) & freeRightDiag;
                    }
                }
            }
            //w lewo do góry
            if (Long.lowestOneBit(opponentLeftDiag) < queen && freeLeftDiag != 0) {
                long tmp = Long.rotateRight(queen, 4);
                while ((tmp & freeLeftDiag) != 0) {
                    tmp = Long.rotateRight(tmp, 4);
                }
                if ((tmp & opponentLeftDiag) == tmp) {
                    long tmp2 = Long.rotateRight(tmp, 4) & freeLeftDiag;
                    while (tmp2 != 0) {
                        //bicie piona tmp na tmp2
                        long newSideToMove = sideToMove ^ (queen | tmp2);
                        long newOpponent = opponent ^ tmp;
                        long newQueens = queens ^ (queen | (tmp&queens) | tmp2);
                        int targetIndex = 64 - Long.toBinaryString(tmp2).length();
                        String notation = fields[index].toString() + "x" + fields[targetIndex].toString();
                        nextQueenCapture(tmp2, newSideToMove, newOpponent, newQueens, notation, moves, -4, whiteTurn);
                        tmp2 = Long.rotateRight(tmp2, 4) & freeLeftDiag;
                    }
                }
            }
            //w prawo do dołu
            if (Long.highestOneBit(opponentLeftDiag) > queen && freeLeftDiag != 0) {
                long tmp = Long.rotateLeft(queen, 4);
                while ((tmp & freeLeftDiag) != 0) {
                    tmp = Long.rotateLeft(tmp, 4);
                }
                if ((tmp & opponentLeftDiag) == tmp) {
                    long tmp2 = Long.rotateLeft(tmp, 4) & freeLeftDiag;
                    while (tmp2 != 0) {
                        //bicie piona tmp na tmp2
                        long newSideToMove = sideToMove ^ (queen | tmp2);
                        long newOpponent = opponent ^ tmp;
                        long newQueens = queens ^ (queen | (tmp&queens) | tmp2);
                        int targetIndex = 64 - Long.toBinaryString(tmp2).length();
                        String notation = fields[index].toString() + "x" + fields[targetIndex].toString();
                        nextQueenCapture(tmp2, newSideToMove, newOpponent, newQueens, notation, moves, 4, whiteTurn);
                        tmp2 = Long.rotateLeft(tmp2, 4) & freeLeftDiag;
                    }
                }
            }
            queen = Long.highestOneBit(ourQueens);
        }
    }

    private void nextQueenCapture(long queen, long sideToMove, long opponent, long queens, String notation,
            List moves, int forbiddenDirection, boolean whiteTurn) {
        boolean finalCapture = true;
        long unoccupied = ~(sideToMove | opponent) & PERMITTED;
        int index = 64 - Long.toBinaryString(queen).length();
        long rightDiagonal = RIGHT_DIAGONALS[index];
        long leftDiagonal = LEFT_DIAGONALS[index];
        long opponentRightDiag = opponent & rightDiagonal;
        long opponentLeftDiag = opponent & leftDiagonal;
        long freeRightDiag = unoccupied & rightDiagonal;
        long freeLeftDiag = unoccupied & leftDiagonal;
        long opponentDiag;
        long freeDiag;
        for (int dir : directions) {
            if (dir == forbiddenDirection) {
                continue;
            }
            if (Math.abs(dir) == 5) {
                opponentDiag = opponentRightDiag;
                freeDiag = freeRightDiag;
            } else {
                opponentDiag = opponentLeftDiag;
                freeDiag = freeLeftDiag;
            }
            boolean isOpponentInDirection = (dir > 0) ? Long.lowestOneBit(opponentDiag) < queen : Long.highestOneBit(opponentDiag) > queen;
            if (isOpponentInDirection && freeDiag != 0) {
                long tmp = Long.rotateRight(queen, dir);
                while ((tmp & freeDiag) > 0) {
                    tmp = Long.rotateRight(tmp, dir);
                }
                if ((tmp & opponentDiag) == tmp) {
                    long tmp2 = Long.rotateRight(tmp, dir) & freeDiag;
                    while (tmp2 != 0) {
                        finalCapture = false;
                        long newSideToMove = sideToMove ^ (queen | tmp2);
                        long newOpponent = opponent ^ tmp;
                        long newQueens = queens ^ (queen | (tmp&queens) | tmp2);
                        int targetIndex = 64 - Long.toBinaryString(tmp2).length();
                        String newNotation = notation + "x" + fields[targetIndex].toString();
                        nextQueenCapture(tmp2, newSideToMove, newOpponent, newQueens, newNotation, moves, -dir, whiteTurn);
                        tmp2 = Long.rotateRight(tmp2, dir) & freeDiag;
                    }
                }
            }
        }

        if (finalCapture) {
            if (notation.length() < longestCapture) {
                return;
            } else {
                longestCapture = notation.length();
            }
            Fields source = Fields.valueOf(notation.substring(0, 2));
            Fields target = Fields.valueOf(notation.substring(notation.length() - 2, notation.length()));
            String shortNotation = source.toString() + "x" + target.toString();
            BoardPosition position;
            if(whiteTurn)
                position = new BoardPosition(sideToMove, opponent, queens);
            else
                position = new BoardPosition(opponent, sideToMove, queens);
            position.computeHashAndLockCode();
            Move m = new Move(position, source, target, notation, shortNotation, false);
            moves.add(m);
        }

    }

    private void generateQueenMoves(long sideToMove, long opponent, long queens, List moves, boolean whiteTurn,
            int hashCode, int lockCode) {
        long ourQueens = sideToMove & queens;
        if (Long.highestOneBit(ourQueens) == 0) {
            return;
        }
        long unoccupied = ~(sideToMove | opponent) & PERMITTED;
        long queen = Long.highestOneBit(ourQueens);
        while (queen != 0) {
            ourQueens ^= queen;
            int index = 64 - Long.toBinaryString(queen).length();
            Fields from = fields[index];
            long rightDiagonal = RIGHT_DIAGONALS[index];
            long leftDiagonal = LEFT_DIAGONALS[index];
            long freeRightDiag = unoccupied & rightDiagonal;
            long freeLeftDiag = unoccupied & leftDiagonal;
            if (freeRightDiag == (rightDiagonal^queen)) {
                long targetField = Long.highestOneBit(freeRightDiag);
                while (targetField != 0) {
                    freeRightDiag ^= targetField;
                    addQueenMove(queen, targetField, sideToMove, opponent, queens, from, index, moves, whiteTurn, hashCode, lockCode);
                    targetField = Long.highestOneBit(freeRightDiag);
                }
            } else {
                long targetField = Long.rotateRight(queen, 5);
                while ((targetField & freeRightDiag) != 0) {
                    addQueenMove(queen, targetField, sideToMove, opponent, queens, from, index, moves, whiteTurn, hashCode, lockCode);
                    targetField = Long.rotateRight(targetField, 5);
                }
                targetField = Long.rotateRight(queen, -5);
                while ((targetField & freeRightDiag) != 0) {
                    addQueenMove(queen, targetField, sideToMove, opponent, queens, from, index, moves, whiteTurn, hashCode, lockCode);
                    targetField = Long.rotateRight(targetField, -5);
                }
            }
            if(freeLeftDiag == (leftDiagonal ^ queen)) {
                long targetField = Long.highestOneBit(freeLeftDiag);
                while(targetField != 0) {
                    freeLeftDiag ^= targetField;
                    addQueenMove(queen, targetField, sideToMove, opponent, queens, from, index, moves, whiteTurn, hashCode, lockCode);
                    targetField = Long.highestOneBit(freeLeftDiag);
                }
            } else {
                long targetField = Long.rotateRight(queen, 4);
                while((targetField & freeLeftDiag) != 0) {
                    addQueenMove(queen, targetField, sideToMove, opponent, queens, from, index, moves, whiteTurn, hashCode, lockCode);
                    targetField = Long.rotateRight(targetField, 4);
                }
                targetField = Long.rotateRight(queen, -4);
                while((targetField & freeLeftDiag) != 0) {
                    addQueenMove(queen, targetField, sideToMove, opponent, queens, from, index, moves, whiteTurn, hashCode, lockCode);
                    targetField = Long.rotateRight(targetField, -4);
                }
            }
            queen = Long.highestOneBit(ourQueens);
        }
    }

    private void addQueenMove(long queen, long targetField, long sideToMove, long opponent, long queens, 
            Fields from, int sourceIndex, List<Move> moves, boolean whiteTurn, int hashCode, int lockCode) {
        int targetIndex = 64 - Long.toBinaryString(targetField).length();
        Fields to = fields[targetIndex];
        long newSideToMove = sideToMove ^ (queen | targetField);
        long newQueens = queens ^ (queen | targetField);
        BoardPosition position;
        if(whiteTurn) {
            position = new BoardPosition(newSideToMove, opponent, newQueens);
            hashCode ^= HASH_RANDOM_TABLE[sourceIndex][2] ^ HASH_RANDOM_TABLE[targetIndex][2];
            lockCode ^= LOCK_RANDOM_TABLE[sourceIndex][2] ^ LOCK_RANDOM_TABLE[targetIndex][2];
        }
        else {
            position = new BoardPosition(opponent, newSideToMove, newQueens);
            hashCode ^= HASH_RANDOM_TABLE[sourceIndex][3] ^ HASH_RANDOM_TABLE[targetIndex][3];
            lockCode ^= LOCK_RANDOM_TABLE[sourceIndex][3] ^ LOCK_RANDOM_TABLE[targetIndex][3];
        }
        position.setHashCode(hashCode);
        position.setLockCode(lockCode);
        //position.computeHashAndLockCode();
        String notation = from.toString() + "-" + to.toString();
        Move m = new Move(position, from, to, notation, notation, false);
        moves.add(m);
    }

    private void printSetFields(long state) {
        char[] c = Long.toBinaryString(state).toCharArray();
        int zeros = Long.numberOfLeadingZeros(state);
        int translation = (zeros > 0) ? zeros : 0;
        try {
            for (int i = c.length - 1; i >= 0; i--) {
                if (c[i] == '1') {
                    System.out.print(fields[i + translation] + ", ");
                }
            }
        } catch (IndexOutOfBoundsException e) {
            System.out.println("c size: " + c.length);
            System.out.println("zeros: " + zeros);
            System.out.println("translation: " + translation);
        }
        System.out.println();
    }

    private void removeRedundantCaptures(List<Move> moves, int longestCapture) {
        for (int i = moves.size() - 1; i >= 0; i--) {
            if (moves.get(i).getNotation().length() < longestCapture) {
                moves.remove(i);
            }
        }
    }
}
